package doing;

import com.study.common.ListNode;
import org.junit.Test;

import java.util.Random;

import static com.study.util.LogUtil.info;

/**
 * 382. Linked List Random Node 链表随机节点
 * <p>
 * 给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
 * <p>
 * 进阶:
 * 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
 * <p>
 * 2019-05-19 18:05
 **/
@SuppressWarnings("all")
public class LinkedListRandomNode {

    class Solution {

        private ListNode node;

        public Solution(ListNode head) {
            // TODO
            node = head;
        }

        public int getRandom() {
            // TODO
            ListNode res = node;
            ListNode cur = node.next;

            int i = 2;
            //从第二个节点开始,每次循环替换res的概率都是1/i
            while (cur != null) {
                if (new Random().nextInt(i) == 0)
                    res = cur;

                cur = cur.next;
                i++;
            }
            return res.val;
        }
    }

    @Test
    public void test() {
        // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
        info(new Solution(new ListNode(1, 2, 3)).getRandom());
    }
}























/*
private ListNode node;

public Solution(ListNode head) {
    node = head;
}

public int getRandom() {
    ListNode res = node;
    ListNode cur = node.next;

    int i = 2;
    //从第二个节点开始,每次循环替换res的概率都是1/i
    while (cur != null) {
        int ran = new Random().nextInt(i);
        if (ran == 0) {
            res = cur;
        }
        cur = cur.next;
        i++;
    }
    return res.val;
}
*/
